题意

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.

不使用乘法、除法、取余操作计算两个数的商，若溢出，返回MAX_INT。

思路

被除数记为x，除数记为y：

若将除数y左移n次后可得到不大于除数的最大的数，也即y×(2n)是不大于除数的最大的数，这时，已经计算出了原被除数中至少可以减2n个除数，x-y×(2n) 是被除数余下的部分，只要继续计算余下的部分并记录减去除数的y的个数，直到余下的部分小于y 。

以1003/7为例：

  1. 1003-7×27=1003-896=107 （896×2>1003，所以896是除数移位后最大的不大于被除数1003的数），一共移位了7次，减去27=128个除数。

  2. 107-7×23=107-56 =51，移位3次，减去了8个除数。

  3. 51-7×22=51-28=23，移位2次，减去了4个除数。

  4. 23-7×21=23-14=9，移位1次，减去了2个除数。

  5. 9-7×20=9-7=2，移位0次，减去了1个除数。

  6. 2<7，算法结束。

得到1003/7的运算结果为128+8+4+2+1=143。

事实上，最终得到的商在计算机内部是一定长度的连续的二进制位，这种算法就可以理解为由高位到低位逐一试探出商的一个二进制位，是快速幂[LeetCode 50. Pow(x,n)]的应用。

又从二进制位的角度来观察该算法：（只看低16位，高位全0）

  1. 00000000 00000001移位7次得到 00000000 10000000，即1003-7×27=1000-896=107

  2. 00000000 00000001移位3次得到 00000000 00001000，即107-7×23=104-56=51

  3. 00000000 00000001移位2次得到 00000000 00000100，即51-7×22=51-28=23

  4. 00000000 00000001移位1次得到 00000000 00000010，即23-7×21=23-14=9

  5. 00000000 00000001移位1次得到 00000000 00000001，即9-7×20=9-7=2

  6. 2<7，算法结束。

得到1000/7的运算结果为：00000000 10000000 | 00000000 00001000 | 00000000 00000100 | 00000000 00000010 | 00000000 00000001 = 00000000 10001111，化为十进制为143。

需要注意的地方

计算机中整数用补码表示，对于一个32位的int类型，最小的数是0x80000000=-2147483648，最大的数是0x7FFFFFFF=2147483647，问题来了，负数比正数多一个，那么-2147483648/-1=2147483647，超过了计算机所能表示的正数的最大值，类似地，-(-2147483648)也无法得到正确结果。

程序可以使用64位整数处理所有中间过程，最后再判断输出结果是否得到了0x80000000 这个值（事实上，当且仅当0x80000000/-1会出现溢出的情况），若是，题目要求输出INT_MAX=0x7FFFFFFF。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int divide(int dividend, int divisor)
{
    long long divd = dividend, divs = divisor;
    bool nag = false;
    if((divd < 0 && divs > 0) || (divd > 0 && divs < 0))
    {
        if(divd < 0) divd = -divd;
        if(divs < 0) divs = -divs;
        nag = true;
    }
    if(divd < 0 && divs < 0)
    {
        divd = -divd;
        divs = -divs;
    }
    long long ret = 0;
    while(divd >= divs)
    {
        long long t = divs;
        long long i = 1;
        while(true)
        {
            if(t > divd)
            {
                t >>= 1;
                i >>= 1;
                ret += i;
                divd -= t;
                break;
            }
            t <<= 1;
            i <<= 1;
        }
    }
    if(nag) ret = -ret;
    if(ret<INT_MIN || ret>INT_MAX) return 0x7fffffff;
    return (int)ret;
}